package com.wngbms.geektime;

import java.util.Arrays;

public class _01_coin {

    public static void main(String[] args) {
        /*System.out.println(getMinCoinCount());
        System.out.println(getMinCoinCountOfValue());*/
        getMinCoinCountOfValue();
    }

    private static void getMinCoinCountOfValue() {
        // 硬币面值
        int[] values = {5, 3};
//        int[] values = {10, 7, 1};
        // 总价
        int total = 11;
        int minCoinCount = getMinCoinCountOfValueHelper(total, values);

        // 输出结果
        System.out.println(minCoinCount);
    }

    /**
     * @param total 金额
     * @param coins 币种数组，从大到小排序
     * @return 返回币数，如果返回-1表示无法凑够total
     */
    private static int getMinCoinCountOfValueHelper(int total, int[] coins) {
        if (coins.length == 0) {
            return -1;
        }

        //当前币值
        int currentCoin = coins[0];

        //使用当前币值数量
        int useCurrentCoinCount = total / currentCoin;

        int restTotal = total - useCurrentCoinCount * currentCoin;
        // 如果restTotal为0，表示余额已除尽，组合完成
        if (restTotal == 0) {
            return useCurrentCoinCount;
        }

        // 其他币种数量
        int coinCount = -1;
        // 剩余的币种
        int[] restCoins = Arrays.copyOfRange(coins, 1, coins.length);
        while (useCurrentCoinCount >= 0) {
            // 否则尝试用剩余面值求当前余额的硬币总数
            coinCount = getMinCoinCountOfValueHelper(restTotal, restCoins);

            // 如果后续没有有可用组合,退一步，当前useCurrentCoinCount币数减1
            if (coinCount == -1) {
                // 否则尝试把当前面值数-1
                useCurrentCoinCount--;
                // 重新计算restTotal
                restTotal = total - useCurrentCoinCount * currentCoin;

            } else {
                return useCurrentCoinCount + coinCount;
            }
        }

        return -1;
    }

/*

    public static int getMinCoinCountOfValue() {
        int[] values = {5, 3};
        int total = 11;
        int minCoin = getMinCoinCountLoop(total, values, 0);

        return (minCoin == Integer.MAX_VALUE) ? -1 : minCoin;
    }

    private static int getMinCoinCountLoop(int total, int[] values, int k) {
        int minCount = Integer.MAX_VALUE;
        int valueCount = values.length;

        if (k == valueCount) {
            return Math.min(minCount, getMinCoinCountOfValue(total, values, 0));
        }

        for (int i = k; i < valueCount - 1; i++) {
            int t = values[k];
            values[k] = values[i];
            values[i] = t;

            minCount = Math.min(minCount, getMinCoinCountLoop(total, values, k + 1));

            // 回溯
            t = values[k];
            values[k] = values[i];
            values[i] = t;
        }

        return minCount;
    }

    private static int getMinCoinCountOfValue(int total, int[] values, int valueIndex) {
        int valueCount = values.length;
        if (valueIndex == valueCount) {
            return Integer.MAX_VALUE;
        }

        int minResult = Integer.MAX_VALUE;
        int currentValue = values[valueIndex];
        int maxCount = total / currentValue;

        for (int count = maxCount; count >= 0; count--) {
            int rest = total - count * currentValue;
            if (rest == 0) {
                minResult = Math.min(minResult, count);
                break;
            }

            int restCount = getMinCoinCountOfValue(rest, values, valueIndex + 1);

            if (restCount == Integer.MAX_VALUE) {
                if (count == 0) {
                    break;
                }
                continue;
            }

            minResult = Math.min(minResult, count + restCount);
        }

        return minResult;
    }

    public static int getMinCoinCount() {
        int[] values = {5, 3};
        int total = 15;
        return getMinCoinCountHelper(total, values, values.length);
    }

    private static int getMinCoinCountHelper(int total, int[] values, int valueCount) {
        int rest = total;
        int count = 0;

        for (int i = 0; i < valueCount; i++) {
            int currentCount = rest / values[i];
            rest -= currentCount * values[i];
            count += currentCount;

            if (rest == 0) {
                return count;
            }
        }

        return -1;
    }
*/

}
